package ebook.datastructure.typed.chapter8;

import com.google.gson.Gson;
import lombok.Data;
import utils.JsonFormatUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * description: <br>
 * createTime: 2018/11/1317:15 <br>
 *
 * @author zzh
 */
public class BinarySortedTree4Int {

    private Node4Int root;


    public void addNode(int value) {
        Node4Int node = new Node4Int(value);
        addNode(node);
    }


    public void addNode(Node4Int node) {
        if (root == null) {
            root = node;
        } else {
            linkedToNode(node, root);
        }
    }


    private void linkedToNode(Node4Int addedNode, Node4Int node) {
        //允许插入相等的元素，相等的元素放到右节点
        if (addedNode.getValue() >= node.getValue()) {
            if (node.getRight() == null) {
                node.setRight(addedNode);
            } else {
                linkedToNode(addedNode, node.getRight());
            }
        } else {
            if (node.getLeft() == null) {
                node.setLeft(addedNode);
            } else {
                linkedToNode(addedNode, node.getLeft());
            }
        }
    }


    public void outputInList() {
        preVisitAll(System.out::println);
    }


    public void outputInListRevert() {
        postVisitAll(System.out::println);
    }

    //TODO 待完成
    public void displayTree() {
        List<StringBuilder> sbList = new ArrayList<>();
        int totalLevel = displayTree(root, 0, 1, sbList);
    }

    //TODO 待完成
    private int displayTree(Node4Int root, int level, int countLevel, List<StringBuilder> sbList) {
        displayTree();
        return 0;
    }


    /**
     * 前序遍历访问
     * 先遍历当前节点，再左子树，再右子树
     * @param visitor
     */
    public void preVisitAll(Visitor visitor) {
        preVisitAll(root, visitor);
    }


    private void preVisitAll(Node4Int node, Visitor visitor) {
        if (node != null) {
            visitor.visit(node.getValue());
            preVisitAll(node.getLeft(), visitor);
            preVisitAll(node.getRight(), visitor);
        }
    }


    /**
     * 中序遍历访问
     * 先遍历左子树，再当前节点，再右子树
     * @param visitor
     */
    public void midVisitAll(Visitor visitor) {
        midVisitAll(root, visitor);
    }


    private void midVisitAll(Node4Int node, Visitor visitor) {
        if (node != null) {
            midVisitAll(node.getLeft(), visitor);
            visitor.visit(node.getValue());
            midVisitAll(node.getRight(), visitor);
        }
    }


    /**
     * 后序遍历访问
     * 先遍历左子树，再右子树，再当前节点
     * @param visitor
     */
    public void postVisitAll(Visitor visitor) {
        postVisitAll(root, visitor);
    }


    private void postVisitAll(Node4Int node, Visitor visitor) {
        if (node != null) {
            postVisitAll(node.getLeft(), visitor);
            postVisitAll(node.getRight(), visitor);
            visitor.visit(node.getValue());
        }
    }


    public List<Node4Int> find(int value) {
        return find(value, root);
    }


    private List<Node4Int> find(int value, Node4Int node) {
        List<Node4Int> result = new ArrayList<>();
        if (node == null) {
            return result;
        }
        if (node.getValue() == value) {
            result.add(node);
            result.addAll(find(value, node.getRight()));
            return result;
        }
        if (node.getValue() < value) {
            return find(value, node.getRight());
        }
        return find(value, node.getLeft());
    }


    public void deleteNode(Node4Int node) {

    }


    public void deleteNodeByValue(int value) {
        deleteNodeByValue(null, root, value);
    }


    private void deleteNodeByValue(Node4Int parentNode, Node4Int node, int value) {
        if (node == null) {
            return;
        }
        if (node.getValue() == value) {
            deleteNodeByValue(node, node.getRight(), value);
            delete(parentNode, node);
        } else if (node.getValue() > value) {
            deleteNodeByValue(node, node.getLeft(), value);
        } else {
            deleteNodeByValue(node, node.getRight(), value);
        }
    }


    private void delete(Node4Int parentNode, Node4Int node) {
        //没有子节点
        if(node.getRight() == null && node.getLeft() == null) {
            replaceSonNode(parentNode, node, null);
            return;
        }

        //有两个子节点
        if(node.getRight() != null && node.getLeft() != null) {
            Node4Int backNode = getBackNode(node, node.getRight());
            backNode.setLeft(node.getLeft());
            Node4Int rightBackNode = backNode;
            while(rightBackNode.getRight() != null && rightBackNode.getRight().getValue() == backNode.getValue()) {
                rightBackNode = backNode.getRight();
            }
            rightBackNode.setRight(node.getRight());
            replaceSonNode(parentNode, node, backNode);
            return;
        }

        //有一个子节点
        if(node.getRight() != null) {
            replaceSonNode(parentNode, node, node.getRight());
        } else {
            replaceSonNode(parentNode, node, node.getLeft());
        }

    }


    private Node4Int getBackNode(Node4Int parentNode, Node4Int node) {
        if(node == null) {
            return null;
        }
        if(node.getLeft() == null) {
            Node4Int deletedNode = node;
            while(deletedNode.getRight() != null && deletedNode.getRight().getValue() == node.getValue()) {
                deletedNode = node.getRight();
            }

            delete(parentNode, deletedNode);
            return node;
        }
        return getBackNode(node, node.getLeft());
    }


    private void replaceSonNode(Node4Int parentNode, Node4Int oldNode, Node4Int newNode) {
        if(parentNode == null) {
            root = newNode;
            return;
        }
        if(parentNode.getValue() > oldNode.getValue()) {
            parentNode.setLeft(newNode);
        } else {
            parentNode.setRight(newNode);
        }
    }


    /**
     * 查找最大的节点
     * @return
     */
    public List<Node4Int> findMaxNodes() {
        List<Node4Int> result = new ArrayList<>();
        if(root != null) {
            Node4Int rightNode = root;
            Node4Int parentNode = null;
            while(rightNode.getRight() != null) {
                parentNode = rightNode;
                rightNode= rightNode.getRight();
                if(parentNode.getValue() == rightNode.getValue()) {
                    result.add(parentNode);
                } else {
                    result.clear();
                }
            }
            result.add(rightNode);
        }
        return result;
    }


    /**
     * 查找最小的节点
     * @return
     */
    public List<Node4Int> findMinNodes() {
        List<Node4Int> result = new ArrayList<>();
        if(root != null) {
            Node4Int leftNode = root;
            while(leftNode.getLeft() != null) {
                leftNode = leftNode.getLeft();
            }
            result.add(leftNode);
            result.addAll(find(leftNode.getValue(), leftNode.getRight()));
        }
        return result;
    }


    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("{");
        sb.append("\"root\":")
                .append(root);
        sb.append('}');
        return sb.toString();
    }


    @FunctionalInterface
    public interface Visitor {
        void visit(int value);
    }


    public static void main(String[] args) {
        BinarySortedTree4Int tree = new BinarySortedTree4Int();
        tree.addNode(2);
        tree.addNode(5);
        tree.addNode(3);
        tree.addNode(14);
        tree.addNode(4);
        tree.addNode(2);
        tree.addNode(7);
        tree.addNode(9);
        tree.addNode(8);
        tree.addNode(14);
        tree.addNode(13);
        tree.addNode(12);
        tree.addNode(11);
        tree.addNode(2);
        tree.addNode(10);
        tree.addNode(10);
        tree.addNode(14);
        tree.addNode(11);


        tree.addNode(6);
//        tree.outputInList();
//        System.out.println("----------------");
//        tree.outputInListRevert();
//        System.out.println("---------------");
//        List<Node> nodes = tree.find(8);
//        System.out.println(nodes.size());
//        System.out.println("---------------");
//        tree.deleteNodeByValue(9);
//        tree.outputInList();

        System.out.println(JsonFormatUtil.formatJson(new Gson().toJson(tree)));
        System.out.println("----------------------------");
        tree.midVisitAll(System.out::println);
        System.out.println("----------------------------");
        tree.deleteNodeByValue(11);
        tree.midVisitAll(System.out::println);
        System.out.println("----------------------------");
    }
}

@Data
class Node4Int {

    private int value;

    private Node4Int left;

    private Node4Int right;


    public Node4Int(int value) {
        this.value = value;
    }


    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("{");
        sb.append("\"value\":")
                .append(value);
        sb.append(",\"left\":")
                .append(left);
        sb.append(",\"right\":")
                .append(right);
        sb.append('}');
        return sb.toString();
    }
}